package Hot100;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-01-02 14:28
 *
 * 207. 课程表--判断能否修完全部课程---判断是否有环
 * 210. 课程表 II--安排课程顺序
 *
 */
public class canFinish207 {

    /**
     * 207. 课程表
     * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
     * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
     * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
     * 思路：判断有向图是否有环--看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。
     * 有邻接链表将数组转换为图，然后在图中通过回溯遍历边，判断是否有环
     * */
    boolean[] onPath;
    boolean hasCycle=false;
    boolean[] Visited;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        onPath=new boolean[numCourses];
        Visited=new boolean[numCourses];
        //构建图
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        //判断是否有环
        for (int i = 0; i < numCourses; i++) {
            //不一定所有节点都相连，需要以每个节点为起点遍历
            traverse(graph,i);
        }
        return !hasCycle;
    }
    //在graph中遍历s节点
    void traverse(List<Integer>[] graph,int s){
        if (onPath[s]){
            //发现环
            hasCycle=true;return;
        }
        if (Visited[s]) return;
        //前序遍历位置，访问节点
        Visited[s]=true;
        //作出选择，将s加入路径
        onPath[s]=true;
        for (int t:graph[s]) {
            //遍历s出发能到达的点
            traverse(graph,t);
        }
        //离开节点s时需要将s从path上去除。但是s已经被访问过所有visited不会撤销
        onPath[s]=false;
    }
    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites){
        List<Integer>[] graph=new LinkedList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i]=new LinkedList<>();
        }
        for (int[] edge:prerequisites) {
            graph[edge[1]].add(edge[0]);
        }
        return graph;
    }

    /**
     * 210. 课程表 II
     * 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，
     * 表示在选修课程 ai 前 必须 先选修 bi 。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。
     * 如果不可能完成所有课程，返回 一个空数组 。
     * 拓扑排序：直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的
     * 思路：先判断是否有环，有环的图无法拓扑排序
     * 再将后序遍历的结果进行反转，就是拓扑排序的结果。--因为后序遍历先将子节点加入然后再遍历当前，意味着需要先完成依赖项才能完成当前
     * 当构建图时是依赖项->被依赖，则后序遍历结果不需要翻转
     * 当构件图时是被依赖->依赖项，则后序遍历结果需要翻转
     * */
    List<Integer> postOrder=new ArrayList<>();
    boolean hascycle=false;
    boolean[] visited,onpath;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        visited=new boolean[numCourses];
        onpath=new boolean[numCourses];
        //构建图
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        //先判断是否有环
        for (int i = 0; i < numCourses; i++) {
            traverse210(graph,i);
        }
        if (hascycle) return new int[]{};
        //没有环，进行拓扑排序，将后序遍历的结果翻转即可
        int[] res=new int[numCourses];
        Collections.reverse(postOrder);
        for (int i = 0; i < numCourses; i++) {
            res[i]=postOrder.get(i);
        }
        return res;
    }
    void traverse210(List<Integer>[] graph,int s){
        if (onpath[s]) {
            hascycle=true;
            return;
        }
        if (visited[s]) return;
        //前序遍历位置
        visited[s]=true;
        onpath[s]=true;
        for (int t:graph[s]) {
            traverse210(graph,t);
        }
        //后序遍历位置
        postOrder.add(s);
        onpath[s]=false;
    }

}
